import java.util.Stack;

//找两个节点的最近公共祖先
//第二种方法：
//如求两个链表的交点，只要根节点不为空，入栈，为空，出栈
class Solution1 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root,
                                         TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root, p, stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, q, stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if (size1 > size2) {
            int index = size1 - size2;
            while (index != 0) {
                stack1.pop();
                index--;
            }
        } else {
            int index = size2 - size1;
            while (index != 0) {
                stack2.pop();
                index--;
            }
        }
            while (stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }
            return stack1.pop();

    }
    private boolean getPath(TreeNode root, TreeNode node,Stack<TreeNode>stack){
        if(root==null||node==null){
            return  false;
        }
        stack.push(root);
        if(root==node){
            return  true;
        }
        boolean flag1=getPath(root.left,node,stack);
        if(flag1==true){
            return true;
        }
        boolean flag2=getPath(root.right,node,stack);
        if(flag2==true){
            return true;
        }
        stack.pop();
        return false;
    }
}